/* PROBLEME N° 14
 * Quel nombre en dessous de 1000000 génère
 * la plus longue suite de Syracuse (s'arrêtant à 1)
 *
 * Date de résolution : Mar. 09 Fev. 2010 19:51
 * Temps d'exécution : 0m0.141s
 * Résultat : 837799 avec une suite de longueur 525
 */
#include <stdio.h>
#include <stdlib.h>

#define N 1000001

static unsigned long long tab[N];

unsigned long long syracuse(unsigned long long);
unsigned long long calculNbreTermes(unsigned long long);

int main(int argc, char * argv[])
{
    int i = 0, max = 0;
    unsigned long long nbreTermes = 0, maxNbreTermes = 0;

    for(i = 1; i < N; ++i)
    {
        nbreTermes = calculNbreTermes(i);
        if(nbreTermes >= maxNbreTermes)
        {
            maxNbreTermes = nbreTermes;
            max = i;
        }
    }

    printf("Max = %d\n", max);
    printf("Nbre de termes = %lld\n", maxNbreTermes);

    return 0;
}

// Renvoie le successeur de n dans la suite de Syracuse
unsigned long long syracuse(unsigned long long n)
{
    if(n % 2 == 0)
        return n / 2;
    else 
        return 3 * n + 1;
}

unsigned long long calculNbreTermes(unsigned long long n)
{
    if(n == 1)
        return 1;
    else
    {
        if(n < N && tab[n] != 0)
            return tab[n];
        if(n < N)
        {
            tab[n] = 1 + calculNbreTermes(syracuse(n));
            return tab[n];
        }
        else
            return 1 + calculNbreTermes(syracuse(n));
    }
}
